//给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。 
//
// 
//
// 示例： 
//
// 输入：[1,2,3,4,5,null,7,8]
//
//        1
//       /  \ 
//      2    3
//     / \    \ 
//    4   5    7
//   /
//  8
//
//输出：[[1],[2,3],[4,5,7],[8]]
// 
//
// Related Topics 树 广度优先搜索 链表 二叉树 👍 103 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-07-01 22:33:42
 * @description 面试题 04.03.特定深度节点链表
 */
public class ListOfDepthLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ListOfDepthLcci fun=new ListOfDepthLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
         this.left = left;
          this.right = right;
      }
  }


 // Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
		 // 其实就是层次遍历
    public ListNode[] listOfDepth(TreeNode tree) {
		List<ListNode> res=new ArrayList<>();
		Deque<TreeNode> q=new ArrayDeque<>();
		q.offer(tree);
		while (!q.isEmpty()){
			int size=q.size();
			ListNode t=new ListNode();
			ListNode p=t;
			while (size-->0){
				TreeNode pop = q.poll();
				if(pop.left!=null) q.offer(pop.left);
				if(pop.right!=null) q.offer(pop.right);
				t.next=new ListNode(pop.val);
				t=t.next;
			}
			res.add(p.next);
		}
		return res.toArray(new ListNode[0]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
